package mo.offer_special;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class L082 {

    private List<int[]> frequency = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> results = new ArrayList<>();
        List<Integer> combination = new ArrayList<>();

        Arrays.sort(candidates);
        for (int i = 0; i < candidates.length; i++) {
            int size = frequency.size();
            if (size == 0 || frequency.get(size-1)[0] != candidates[i]) {
                frequency.add(new int[]{candidates[i], 1});
            } else {
                frequency.get(size-1)[1]++;
            }
        }

        dfs(results, combination, target, 0);
        return results;
    }

    private void dfs(List<List<Integer>> results, List<Integer> combination, int target, int index) {
        if (target == 0) {
            results.add(new ArrayList<>(combination));
            return;
        }

        if (index == frequency.size() || target < frequency.get(index)[0]) {
            return;
        }
        dfs(results, combination, target, index+1);

        int most = Math.min(target / frequency.get(index)[0], frequency.get(index)[1]);
        for (int i = 1; i <= most; i++) {
            combination.add(frequency.get(index)[0]);
            dfs(results, combination, target - i*frequency.get(index)[0], index+1);
        }

        //解决最外层的递归
        for (int i = 1; i <= most; i++) {
            combination.remove(combination.size()-1);
        }
    }

    public static void main(String[] args) {
        L082 test = new L082();
        System.out.println(test.combinationSum2(new int[]{1, 2, 5}, 8));
    }

}
